// https://leetcode.cn/problems/contains-duplicate-ii/

// 个，模仿【最长无重复字符的子串】
// class Solution {
// public:
//     bool containsNearbyDuplicate(vector<int>& nums, int k) {
//         map<int, int> rec;
//         int j = 0;
//         for (int i = 0; i < nums.size(); ++i) {
//             while (j < nums.size() && rec[nums[j]] == 0) {
//                 rec[nums[j++]] = 1;
//             }
//             if (j >= nums.size()) break;
//             if (j - i <= k) return true;
//             rec[nums[i]] = 0;
//         }
//         return false;
//     }
// };

// 直接哈希表记录位置
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> rec;
        for (int i = 0; i < nums.size(); ++i) {
            if (rec.find(nums[i]) != rec.end() && i - rec[nums[i]] <= k) return true;
            rec[nums[i]] = i; 
        }
        return false;
    }
};

//滑动窗口，维护一个长度为k+1的哈希集
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> rec;
        for (int i = 0; i < nums.size(); ++i) {
            if (rec[nums[i]]) return true;
            rec[nums[i]] = 1;
            if (i >= k) rec[nums[i - k]] = 0;
        }
        return false;
    }
};